package com.atguigu.algorithm;

import java.util.Stack;

class ListNode{
    public int val;
    public ListNode next;
    public ListNode(int val){
        this.val=val;
    }
}
public class MonotonyStack {
    public static void main(String[] args) {
        int[] arr=new int[]{5,4,3,4,5,3,5,6};
        theTwoSideOfBiggerNum(arr);
    }
    public static void theTwoSideOfBiggerNum(int[] nums){
        if(nums==null || nums.length==0){
            return;
        }
        Stack<ListNode> stack=new Stack<>();
        for(int i=0;i<nums.length;i++){
            if(stack.isEmpty()){
                stack.push(new ListNode(i));//若栈为空直接放入
                continue;
            }
            //栈不为空，开始比较栈顶元素指与要放入值的大小
            //栈顶元素比待放入元素大，直接放置
            if(nums[stack.peek().val]>nums[i]){
                stack.push(new ListNode(i));
            }else{ //栈顶元素比待入值小于或等于
                //栈顶元素小于待入值，同时栈不为空
                while(!stack.isEmpty() && nums[stack.peek().val]<nums[i]) {
                    //小于的情况
                    ListNode tmp = stack.pop(); //出栈
                    while (tmp != null) {
                        System.out.print(tmp.val + "的右近大值为:" + i + "其值为:" + nums[i] + "  ");
                        //看左边最大值时,下一个值为空的情况下
                        if (stack.isEmpty()) {
                            System.out.print(tmp.val + "的左近大值为:无");
                        }
                        //下一个值不为空，拿到该值，遍历到链表的最后一个节点
                        if(!stack.isEmpty()) {
                            ListNode head = stack.peek();
                            while (head.next != null) {
                                head = head.next;
                            }
                            System.out.print(tmp.val + "左近大值为:" + head.val + "其值为：" + nums[head.val]);
                        }
                        System.out.println();
                        tmp=tmp.next;
                    }
                    if(stack.isEmpty()){
                        break;
                    }
                }
                //出循环时，要么栈为空，要么当前的值小于
                if(stack.isEmpty() || nums[stack.peek().val]>nums[i]){
                    stack.push(new ListNode(i));
                    continue;
                }
                //等于的情况,拿到该节点，遍历到最后一个节点，接上新节点
                ListNode tmp=stack.peek();
                while(tmp.next!=null){
                    tmp=tmp.next;
                }
                tmp.next=new ListNode(i);
            }
        }
        //此时栈如果不为空，则继续遍历
        while(!stack.isEmpty()){
            ListNode cur=stack.pop();
            while(cur!=null){
                System.out.print(cur.val+"的右近大值为:无   ");
                if(stack.isEmpty()){
                    System.out.println( cur.val+"的左近大值为:无");
                }else{
                    ListNode tmp=stack.peek();
                    while(tmp.next!=null){
                        tmp=tmp.next;
                    }
                    System.out.println(cur.val+"的右近大值为:"+tmp.val+"  其值为:"+nums[tmp.val]);
                }
                System.out.println();
                cur=cur.next;
            }
        }
    }
}
